package offer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhanBo
 * @date 2020/6/13
 */
public class Solution53 {
    public static void main(String[] args) {
        /*int [] nums = {5,7,7,8,8,10};
        System.out.println(search(nums, 8));*/
        int [] nums = {0,1,2,4,5,6};
        System.out.println(missingNumber(nums));
    }

    /**
     * 面试题53 - I. 在排序数组中查找数字 I
     *
     * 统计一个数字在排序数组中出现的次数。
     *
     * 输入: nums = [5,7,7,8,8,10], target = 8
     * 输出: 2
     * @param nums
     * @param target
     * @return
     */
    public static int search(int[] nums, int target) {
        Map<Integer,Integer> map = new HashMap<>(64);
        for (int item : nums){
            if (map.containsKey(item)){
                map.put(item,map.get(item)+1);
            }else {
                map.put(item,1);
            }
        }
        return map.getOrDefault(target, 0);
    }


    /**
     *
     * @param nums
     * @param target
     * @return
     */
    public int search2(int[] nums, int target) {
        // 搜索右边界 right
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) {
            return 0;
        }
        // 搜索左边界 right
        i = 0; j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] < target) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        int left = j;
        return right - left - 1;
    }

    /**
     *
     * @param nums
     * @param target
     * @return
     */
    public int search3(int[] nums, int target) {
        return helper(nums, target) - helper(nums, target - 1);
    }

    int helper(int[] nums, int tar) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] <= tar) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }


    /**
     * 剑指 Offer 53 - II. 0～n-1中缺失的数字
     * 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。
     * 在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
     *
     * 输入: [0,1,3]
     * 输出: 2
     *
     * 输入: [0,1,2,3,4,5,6,7,9]
     * 输出: 8
     *
     * @param nums
     * @return
     */
    public static int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length-1;
        while (left<=right){
            int mid = (left+right)/2;
            //如果nums[mid] != mid ，缺失的数字肯定在左数组，如果等于缺失的数字在右数组
            if (nums[mid] ==mid){
                left = mid+1;
            }else {
                right = mid-1;
            }
        }
        return left;
    }
}
